ebab7d0da53c51438720d60c6e2e467c - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Hopcroft–Karp algorithm</title>

</head>

Hopcroft–Karp algorithm

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .infobox-subbox{padding:0;border:none;margin:-3px;width:auto;min-width:100%;font-size:100%;clear:none;float:none;background-color:transparent}.mw-parser-output .infobox-3cols-child{margin:auto}.mw-parser-output .infobox .navbar{font-size:100%}@media screen{html.skin-theme-clientpref-night .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media(min-width:640px){body.skin--responsive .mw-parser-output .infobox-table{display:table!important}body.skin--responsive .mw-parser-output .infobox-table>caption{display:table-caption!important}body.skin--responsive .mw-parser-output .infobox-table>tbody{display:table-row-group}body.skin--responsive .mw-parser-output .infobox-table th,body.skin--responsive .mw-parser-output .infobox-table td{padding-left:inherit;padding-right:inherit}}

/* end https://en.wikipedia.org/ */

</style><table class="infobox"><caption class="infobox-title">Hopcroft–Karp algorithm</caption><tbody><tr><th scope="row" class="infobox-label">Class</th><td class="infobox-data">Graph algorithm</td></tr><tr><th scope="row" class="infobox-label">Data structure</th><td class="infobox-data"><a href="Graph_(data_structure)" class="mw-redirect" title="Graph (data structure)">Graph</a></td></tr><tr><th scope="row" class="infobox-label"><a href="Best%2C_worst_and_average_case" title="Best, worst and average case">Worst-case</a> <a href="Time_complexity" title="Time complexity">performance</a></th><td class="infobox-data"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(E{\sqrt {V}})}">

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(E{\sqrt {V}})}</annotation>

</semantics>

</math><img src="./1c594e372d320223b883f70bacc1fd5171966f02.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.081ex; height:3.176ex;" alt="{\displaystyle O(E{\sqrt {V}})}" loading="lazy"></td></tr><tr><th scope="row" class="infobox-label"><a href="Best%2C_worst_and_average_case" title="Best, worst and average case">Worst-case</a> <a href="Space_complexity" title="Space complexity">space complexity</a></th><td class="infobox-data"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(V)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(V)}</annotation>

</semantics>

</math><img src="./44d40b1ca90fee2a2f7e0b3bddac30284ba828af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.37ex; height:2.843ex;" alt="{\displaystyle O(V)}" loading="lazy"></td></tr></tbody></table>

In <a href="Computer_science" title="Computer science">computer science</a>, the Hopcroft–Karp algorithm (sometimes more accurately called the Hopcroft–Karp–Karzanov algorithm)<a href="#cite_note-1">[1]</a> is an <a href="Algorithm" title="Algorithm">algorithm</a> that takes a <a href="Bipartite_graph" title="Bipartite graph">bipartite graph</a> as input and produces a <a href="Maximum-cardinality_matching" class="mw-redirect" title="Maximum-cardinality matching">maximum-cardinality matching</a> as output — a set of as many edges as possible with the property that no two edges share an endpoint. It runs in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(|E|{\sqrt {|V|}})}">

</mrow>

</mrow>

<msqrt>

</mrow>

</mrow>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(|E|{\sqrt {|V|}})}</annotation>

</semantics>

</math><img src="./362a8b01b34078ce125908a35c39d5e59b71cc84.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:12.057ex; height:4.843ex;" alt="{\displaystyle O(|E|{\sqrt {|V|}})}" loading="lazy"> time in the <a href="Worst_case" class="mw-redirect" title="Worst case">worst case</a>, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E}</annotation>

</semantics>

</math><img src="./4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}" loading="lazy"> is set of edges in the graph, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math><img src="./af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy"> is set of vertices of the graph, and it is assumed that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |E|=\Omega (|V|)}">

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |E|=\Omega (|V|)}</annotation>

</semantics>

</math><img src="./3f7afb47b7b7f453dd386b3067c131754c31dd69.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.736ex; height:2.843ex;" alt="{\displaystyle |E|=\Omega (|V|)}" loading="lazy">. In the case of <a href="Dense_graph" title="Dense graph">dense graphs</a> the time bound becomes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(|V|^{2.5})}">

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(|V|^{2.5})}</annotation>

</semantics>

</math><img src="./b4aed9fa0f6aa2e128ea266865e5413e155893e5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.997ex; height:3.343ex;" alt="{\displaystyle O(|V|^{2.5})}" loading="lazy">, and for sparse <a href="Random_graph" title="Random graph">random graphs</a> it runs in time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(|E|\log |V|)}">

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(|E|\log |V|)}</annotation>

</semantics>

</math><img src="./22c52b62d653c3f6686207ef2b6b5907dcd8b5ac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.479ex; height:2.843ex;" alt="{\displaystyle O(|E|\log |V|)}" loading="lazy"> with high probability.<a href="#cite_note-FOOTNOTEBastMehlhornSchäferTamaki2006-2">[2]</a>

The algorithm was discovered by <a href="John_Hopcroft" title="John Hopcroft">John Hopcroft</a> and <a href="Richard_Karp" class="mw-redirect" title="Richard Karp">Richard Karp</a> (<a href="#CITEREFHopcroftKarp1973">1973</a>) and independently by <a href="Alexander_V._Karzanov" title="Alexander V. Karzanov">Alexander Karzanov</a> (<a href="#CITEREFKarzanov1973">1973</a>).<a href="#cite_note-FOOTNOTEDinitz2006-3">[3]</a> As in previous methods for matching such as the <a href="Hungarian_algorithm" title="Hungarian algorithm">Hungarian algorithm</a> and the work of <a href="#CITEREFEdmonds1965">Edmonds (1965)</a>, the Hopcroft–Karp algorithm repeatedly increases the size of a partial matching by finding augmenting paths. These paths are sequences of edges of the graph, which alternate between edges in the matching and edges out of the partial matching, and where the initial and final edge are not in the partial matching. Finding an augmenting path allows us to increment the size of the partial matching, by simply toggling the edges of the augmenting path (putting in the partial matching those that were not, and vice versa). Simpler algorithms for bipartite matching, such as the <a href="Ford%E2%80%93Fulkerson_algorithm" title="Ford–Fulkerson algorithm">Ford–Fulkerson algorithm</a>‚ find one augmenting path per iteration: the Hopcroft-Karp algorithm instead finds a maximal set of shortest augmenting paths, so as to ensure that only <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O({\sqrt {|V|}})}">

<msqrt>

</mrow>

</mrow>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O({\sqrt {|V|}})}</annotation>

</semantics>

</math><img src="./71e29921cde091c1bae5116cfc19ff966b7e957a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:8.987ex; height:4.843ex;" alt="{\displaystyle O({\sqrt {|V|}})}" loading="lazy"> iterations are needed instead of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(|V|)}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(|V|)}</annotation>

</semantics>

</math><img src="./3486d00c2ed0f7eb1db550af8f239ad68241a6c5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.664ex; height:2.843ex;" alt="{\displaystyle O(|V|)}" loading="lazy"> iterations. The same performance of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(|E|{\sqrt {|V|}})}">

</mrow>

</mrow>

<msqrt>

</mrow>

</mrow>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(|E|{\sqrt {|V|}})}</annotation>

</semantics>

</math><img src="./362a8b01b34078ce125908a35c39d5e59b71cc84.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:12.057ex; height:4.843ex;" alt="{\displaystyle O(|E|{\sqrt {|V|}})}" loading="lazy"> can be achieved to find maximum-cardinality matchings in arbitrary graphs, with the more complicated algorithm of Micali and Vazirani.<a href="#cite_note-FOOTNOTEPetersonLoui1988-4">[4]</a>

The Hopcroft–Karp algorithm can be seen as a special case of <a href="Dinic's_algorithm" title="Dinic's algorithm">Dinic's algorithm</a> for the <a href="Maximum-flow_problem" class="mw-redirect" title="Maximum-flow problem">maximum-flow problem</a>.<a href="#cite_note-FOOTNOTETarjan1983102-5">[5]</a>

<div class="mw-heading mw-heading2"><h2 id="Augmenting_paths">Augmenting paths</h2></div>

A vertex that is not the endpoint of an edge in some partial matching <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> is called a free vertex. The basic concept that the algorithm relies on is that of an augmenting path, a path that starts at a free vertex, ends at a free vertex, and alternates between unmatched and matched edges within the path. It follows from this definition that, except for the endpoints, all other vertices (if any) in augmenting path must be non-free vertices. An augmenting path could consist of only two vertices (both free) and single unmatched edge between them.

If <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> is a matching, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> is an augmenting path relative to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy">, then the <a href="Symmetric_difference" title="Symmetric difference">symmetric difference</a> of the two sets of edges, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M\oplus P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M\oplus P}</annotation>

</semantics>

</math><img src="./3cfb5fb18860ec50cacc9631de130e499ba314b3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.028ex; height:2.343ex;" alt="{\displaystyle M\oplus P}" loading="lazy">, would form a matching with size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |M|+1}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |M|+1}</annotation>

</semantics>

</math><img src="./c12f6d458cbcd62407177845fdbd12702a6be762.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.739ex; height:2.843ex;" alt="{\displaystyle |M|+1}" loading="lazy">. Thus, by finding augmenting paths, an algorithm may increase the size of the matching.

Conversely, suppose that a matching <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> is not optimal, and let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> be the symmetric difference <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M\oplus M^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M\oplus M^{*}}</annotation>

</semantics>

</math><img src="./51f30a01d0a9b9392b038284d7337f262b402721.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:8.836ex; height:2.509ex;" alt="{\displaystyle M\oplus M^{*}}" loading="lazy"> where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M^{*}}</annotation>

</semantics>

</math><img src="./b6d760e72a9f5f578f8ba166127f0713d56dc589.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.553ex; height:2.343ex;" alt="{\displaystyle M^{*}}" loading="lazy"> is an optimal matching. Because <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M^{*}}</annotation>

</semantics>

</math><img src="./b6d760e72a9f5f578f8ba166127f0713d56dc589.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.553ex; height:2.343ex;" alt="{\displaystyle M^{*}}" loading="lazy"> are both matchings, every vertex has degree at most 2 in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy">. So <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> must form a collection of disjoint cycles, of paths with an equal number of matched and unmatched edges in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy">, of augmenting paths for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy">, and of augmenting paths for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M^{*}}</annotation>

</semantics>

</math><img src="./b6d760e72a9f5f578f8ba166127f0713d56dc589.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.553ex; height:2.343ex;" alt="{\displaystyle M^{*}}" loading="lazy">; but the latter is impossible because <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M^{*}}</annotation>

</semantics>

</math><img src="./b6d760e72a9f5f578f8ba166127f0713d56dc589.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.553ex; height:2.343ex;" alt="{\displaystyle M^{*}}" loading="lazy"> is optimal. Now, the cycles and the paths with equal numbers of matched and unmatched vertices do not contribute to the difference in size between <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M^{*}}</annotation>

</semantics>

</math><img src="./b6d760e72a9f5f578f8ba166127f0713d56dc589.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.553ex; height:2.343ex;" alt="{\displaystyle M^{*}}" loading="lazy">, so this difference is equal to the number of augmenting paths for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy">. Thus, whenever there exists a matching <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M^{*}}</annotation>

</semantics>

</math><img src="./b6d760e72a9f5f578f8ba166127f0713d56dc589.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.553ex; height:2.343ex;" alt="{\displaystyle M^{*}}" loading="lazy"> larger than the current matching <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy">, there must also exist an augmenting path. If no augmenting path can be found, an algorithm may safely terminate, since in this case <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> must be optimal.

An augmenting path in a matching problem is closely related to the <a href="Augmenting_path" class="mw-redirect" title="Augmenting path">augmenting paths</a> arising in <a href="Maximum_flow_problem" title="Maximum flow problem">maximum flow problems</a>, paths along which one may increase the amount of flow between the terminals of the flow. It is possible to transform the bipartite matching problem into a maximum flow instance, such that the alternating paths of the matching problem become augmenting paths of the flow problem. It suffices to insert two vertices, source and sink, and insert edges of unit capacity from the source to each vertex in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U}</annotation>

</semantics>

</math><img src="./458a728f53b9a0274f059cd695e067c430956025.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.783ex; height:2.176ex;" alt="{\displaystyle U}" loading="lazy">, and from each vertex in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math><img src="./af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy"> to the sink; and let edges from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U}</annotation>

</semantics>

</math><img src="./458a728f53b9a0274f059cd695e067c430956025.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.783ex; height:2.176ex;" alt="{\displaystyle U}" loading="lazy"> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math><img src="./af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy"> have unit capacity.<a href="#cite_note-6">[6]</a> A generalization of the technique used in Hopcroft–Karp algorithm to find maximum flow in an arbitrary network is known as <a href="Dinic's_algorithm" title="Dinic's algorithm">Dinic's algorithm</a>.

<div class="mw-heading mw-heading2"><h2 id="Algorithm">Algorithm</h2></div>

The algorithm may be expressed in the following <a href="Pseudocode" title="Pseudocode">pseudocode</a>.

<dl><dd>Input: Bipartite graph <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G(U\cup V,E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G(U\cup V,E)}</annotation>

</semantics>

</math><img src="./b997d7c77f235ff5bcc40f0db2f9d8d336ad7309.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.598ex; height:2.843ex;" alt="{\displaystyle G(U\cup V,E)}" loading="lazy"></dd>

<dd>Output: Matching <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M\subseteq E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M\subseteq E}</annotation>

</semantics>

</math><img src="./ba5e76e6e4ef95d246bd666e9de79f09ce6681bf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.316ex; height:2.343ex;" alt="{\displaystyle M\subseteq E}" loading="lazy"></dd>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M\leftarrow \emptyset }</annotation>

</semantics>

</math><img src="./41f911f375175724137ab53a46c4f7baa66f86d5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.219ex; height:2.509ex;" alt="{\displaystyle M\leftarrow \emptyset }" loading="lazy"></dd>

<dd>repeat

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {P}}\leftarrow \{P_{1},P_{2},\dots ,P_{k}\}}</annotation>

</semantics>

</math><img src="./cdbcc6493ec4e0f210bc94f9b95f3585014d44e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.529ex; height:2.843ex;" alt="{\displaystyle {\mathcal {P}}\leftarrow \{P_{1},P_{2},\dots ,P_{k}\}}" loading="lazy"> maximal set of vertex-disjoint shortest augmenting paths</dd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M\leftarrow M\oplus (P_{1}\cup P_{2}\cup \dots \cup P_{k})}</annotation>

</semantics>

</math><img src="./76d76c2a66fba590042570ac66151ebc20165f92.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:31.293ex; height:2.843ex;" alt="{\displaystyle M\leftarrow M\oplus (P_{1}\cup P_{2}\cup \dots \cup P_{k})}" loading="lazy"></dd></dl></dd>

<dd>until <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {P}}=\emptyset }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {P}}=\emptyset }</annotation>

</semantics>

</math><img src="./a54d24d95f1bbf5d59f8557abc950bfbc3f7de78.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.965ex; height:2.509ex;" alt="{\displaystyle {\mathcal {P}}=\emptyset }" loading="lazy"></dd></dl>

In more detail, let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U}</annotation>

</semantics>

</math><img src="./458a728f53b9a0274f059cd695e067c430956025.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.783ex; height:2.176ex;" alt="{\displaystyle U}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math><img src="./af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy"> be the two sets in the bipartition of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy">, and let the matching from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U}</annotation>

</semantics>

</math><img src="./458a728f53b9a0274f059cd695e067c430956025.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.783ex; height:2.176ex;" alt="{\displaystyle U}" loading="lazy"> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math><img src="./af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy"> at any time be represented as the set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy">.

The algorithm is run in phases. Each phase consists of the following steps.

<ul><li>A <a href="Breadth-first_search" title="Breadth-first search">breadth-first search</a> partitions the vertices of the graph into layers. The free vertices in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U}</annotation>

</semantics>

</math><img src="./458a728f53b9a0274f059cd695e067c430956025.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.783ex; height:2.176ex;" alt="{\displaystyle U}" loading="lazy"> are used as the starting vertices of this search and form the first layer of the partitioning. At the first level of the search, there are only unmatched edges, since the free vertices in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U}</annotation>

</semantics>

</math><img src="./458a728f53b9a0274f059cd695e067c430956025.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.783ex; height:2.176ex;" alt="{\displaystyle U}" loading="lazy"> are by definition not adjacent to any matched edges. At subsequent levels of the search, the traversed edges are required to alternate between matched and unmatched. That is, when searching for successors from a vertex in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U}</annotation>

</semantics>

</math><img src="./458a728f53b9a0274f059cd695e067c430956025.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.783ex; height:2.176ex;" alt="{\displaystyle U}" loading="lazy">, only unmatched edges may be traversed, while from a vertex in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math><img src="./af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy"> only matched edges may be traversed. The search terminates at the first layer <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> where one or more free vertices in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math><img src="./af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy"> are reached.</li>

<li>All free vertices in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math><img src="./af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy"> at layer <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> are collected into a set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F}</annotation>

</semantics>

</math><img src="./545fd099af8541605f7ee55f08225526be88ce57.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.741ex; height:2.176ex;" alt="{\displaystyle F}" loading="lazy">. That is, a vertex <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"> is put into <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F}</annotation>

</semantics>

</math><img src="./545fd099af8541605f7ee55f08225526be88ce57.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.741ex; height:2.176ex;" alt="{\displaystyle F}" loading="lazy"> if and only if it ends a shortest augmenting path.</li>

<li>The algorithm finds a maximal set of vertex disjoint augmenting paths of length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">. (Maximal means that no more such paths can be added. This is different from finding the maximum number of such paths, which would be harder to do. Fortunately, it is sufficient here to find a maximal set of paths.) This set may be computed by <a href="Depth-first_search" title="Depth-first search">depth-first search</a> (DFS) from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F}</annotation>

</semantics>

</math><img src="./545fd099af8541605f7ee55f08225526be88ce57.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.741ex; height:2.176ex;" alt="{\displaystyle F}" loading="lazy"> to the free vertices in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U}</annotation>

</semantics>

</math><img src="./458a728f53b9a0274f059cd695e067c430956025.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.783ex; height:2.176ex;" alt="{\displaystyle U}" loading="lazy">, using the breadth first layering to guide the search: the DFS is only allowed to follow edges that lead to an unused vertex in the previous layer, and paths in the DFS tree must alternate between matched and unmatched edges. Once an augmenting path is found that involves one of the vertices in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F}</annotation>

</semantics>

</math><img src="./545fd099af8541605f7ee55f08225526be88ce57.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.741ex; height:2.176ex;" alt="{\displaystyle F}" loading="lazy">, the DFS is continued from the next starting vertex. Any vertex encountered during the DFS can immediately be marked as used, since if there is no path from it to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U}</annotation>

</semantics>

</math><img src="./458a728f53b9a0274f059cd695e067c430956025.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.783ex; height:2.176ex;" alt="{\displaystyle U}" loading="lazy"> at the current point in the DFS, then that vertex can't be used to reach <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U}</annotation>

</semantics>

</math><img src="./458a728f53b9a0274f059cd695e067c430956025.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.783ex; height:2.176ex;" alt="{\displaystyle U}" loading="lazy"> at any other point in the DFS. This ensures <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(|E|)}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(|E|)}</annotation>

</semantics>

</math><img src="./976fe7f1e011d0dcdb3d6163754c877aaad5187f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.652ex; height:2.843ex;" alt="{\displaystyle O(|E|)}" loading="lazy"> running time for the DFS. It is also possible to work in the other direction, from free vertices in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U}</annotation>

</semantics>

</math><img src="./458a728f53b9a0274f059cd695e067c430956025.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.783ex; height:2.176ex;" alt="{\displaystyle U}" loading="lazy"> to those in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math><img src="./af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy">, which is the variant used in the pseudocode.</li>

<li>Every one of the paths found in this way is used to enlarge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy">.</li></ul>

The algorithm terminates when no more augmenting paths are found in the breadth first search part of one of the phases.

<div class="mw-heading mw-heading2"><h2 id="Analysis">Analysis</h2></div>

Each phase consists of a single breadth first search and a single depth-first search. Thus, a single phase may be implemented in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(|E|)}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(|E|)}</annotation>

</semantics>

</math><img src="./976fe7f1e011d0dcdb3d6163754c877aaad5187f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.652ex; height:2.843ex;" alt="{\displaystyle O(|E|)}" loading="lazy"> time.

Therefore, the first <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\sqrt {|V|}}}">

<msqrt>

</mrow>

</mrow>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\sqrt {|V|}}}</annotation>

</semantics>

</math><img src="./60edc3ae1f7b299b8d29f01b9234d9528dc05f19.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:5.405ex; height:4.843ex;" alt="{\displaystyle {\sqrt {|V|}}}" loading="lazy"> phases, in a graph with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |V|}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |V|}</annotation>

</semantics>

</math><img src="./9ddcffc28643ac01a14dd0fb32c3157859e365a7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.081ex; height:2.843ex;" alt="{\displaystyle |V|}" loading="lazy"> vertices and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |E|}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |E|}</annotation>

</semantics>

</math><img src="./d8c2b9637808cf805d411190b4ae017dbd4ef8d8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.069ex; height:2.843ex;" alt="{\displaystyle |E|}" loading="lazy"> edges, take time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(|E|{\sqrt {|V|}})}">

</mrow>

</mrow>

<msqrt>

</mrow>

</mrow>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(|E|{\sqrt {|V|}})}</annotation>

</semantics>

</math><img src="./362a8b01b34078ce125908a35c39d5e59b71cc84.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:12.057ex; height:4.843ex;" alt="{\displaystyle O(|E|{\sqrt {|V|}})}" loading="lazy">.

Each phase increases the length of the shortest augmenting path by at least one: the phase finds a maximal set of augmenting paths of the given length, so any remaining augmenting path must be longer. Therefore, once the initial <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\sqrt {|V|}}}">

<msqrt>

</mrow>

</mrow>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\sqrt {|V|}}}</annotation>

</semantics>

</math><img src="./60edc3ae1f7b299b8d29f01b9234d9528dc05f19.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:5.405ex; height:4.843ex;" alt="{\displaystyle {\sqrt {|V|}}}" loading="lazy"> phases of the algorithm are complete, the shortest remaining augmenting path has at least <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\sqrt {|V|}}}">

<msqrt>

</mrow>

</mrow>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\sqrt {|V|}}}</annotation>

</semantics>

</math><img src="./60edc3ae1f7b299b8d29f01b9234d9528dc05f19.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:5.405ex; height:4.843ex;" alt="{\displaystyle {\sqrt {|V|}}}" loading="lazy"> edges in it. However, the <a href="Symmetric_difference" title="Symmetric difference">symmetric difference</a> of the eventual optimal matching and of the partial matching M found by the initial phases forms a collection of vertex-disjoint augmenting paths and alternating cycles. If each of the paths in this collection has length at least <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\sqrt {|V|}}}">

<msqrt>

</mrow>

</mrow>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\sqrt {|V|}}}</annotation>

</semantics>

</math><img src="./60edc3ae1f7b299b8d29f01b9234d9528dc05f19.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:5.405ex; height:4.843ex;" alt="{\displaystyle {\sqrt {|V|}}}" loading="lazy">, there can be at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\sqrt {|V|}}}">

<msqrt>

</mrow>

</mrow>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\sqrt {|V|}}}</annotation>

</semantics>

</math><img src="./60edc3ae1f7b299b8d29f01b9234d9528dc05f19.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:5.405ex; height:4.843ex;" alt="{\displaystyle {\sqrt {|V|}}}" loading="lazy"> paths in the collection, and the size of the optimal matching can differ from the size of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> by at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\sqrt {|V|}}}">

<msqrt>

</mrow>

</mrow>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\sqrt {|V|}}}</annotation>

</semantics>

</math><img src="./60edc3ae1f7b299b8d29f01b9234d9528dc05f19.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:5.405ex; height:4.843ex;" alt="{\displaystyle {\sqrt {|V|}}}" loading="lazy"> edges. Since each phase of the algorithm increases the size of the matching by at least one, there can be at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\sqrt {|V|}}}">

<msqrt>

</mrow>

</mrow>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\sqrt {|V|}}}</annotation>

</semantics>

</math><img src="./60edc3ae1f7b299b8d29f01b9234d9528dc05f19.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:5.405ex; height:4.843ex;" alt="{\displaystyle {\sqrt {|V|}}}" loading="lazy"> additional phases before the algorithm terminates.

Since the algorithm performs a total of at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2{\sqrt {|V|}}}">

<msqrt>

</mrow>

</mrow>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2{\sqrt {|V|}}}</annotation>

</semantics>

</math><img src="./8e0a1a79d6f4bc7825b2a4c98de21867feac17cf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:6.567ex; height:4.843ex;" alt="{\displaystyle 2{\sqrt {|V|}}}" loading="lazy"> phases, it takes a total time of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(|E|{\sqrt {|V|}})}">

</mrow>

</mrow>

<msqrt>

</mrow>

</mrow>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(|E|{\sqrt {|V|}})}</annotation>

</semantics>

</math><img src="./362a8b01b34078ce125908a35c39d5e59b71cc84.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:12.057ex; height:4.843ex;" alt="{\displaystyle O(|E|{\sqrt {|V|}})}" loading="lazy"> in the worst case.

In many instances, however, the time taken by the algorithm may be even faster than this worst case analysis indicates. For instance, in the <a href="Average_case_analysis" class="mw-redirect" title="Average case analysis">average case</a> for <a href="Sparse_graph" class="mw-redirect" title="Sparse graph">sparse</a> bipartite <a href="Random_graph" title="Random graph">random graphs</a>, <a href="#CITEREFBastMehlhornSchäferTamaki2006">Bast et al. (2006)</a> (improving a previous result of <a href="#CITEREFMotwani1994">Motwani 1994</a>) showed that with high probability all non-optimal matchings have augmenting paths of <a href="Logarithm" title="Logarithm">logarithmic</a> length. As a consequence, for these graphs, the Hopcroft–Karp algorithm takes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log |V|)}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log |V|)}</annotation>

</semantics>

</math><img src="./278f22c3d1c12e79d217db0cd4c27c66dc2fad87.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.022ex; height:2.843ex;" alt="{\displaystyle O(\log |V|)}" loading="lazy"> phases and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(|E|\log |V|)}">

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(|E|\log |V|)}</annotation>

</semantics>

</math><img src="./22c52b62d653c3f6686207ef2b6b5907dcd8b5ac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.479ex; height:2.843ex;" alt="{\displaystyle O(|E|\log |V|)}" loading="lazy"> total time.

<div class="mw-heading mw-heading2"><h2 id="Comparison_with_other_bipartite_matching_algorithms">Comparison with other bipartite matching algorithms</h2></div>

For <a href="Sparse_graph" class="mw-redirect" title="Sparse graph">sparse graphs</a>, the Hopcroft–Karp algorithm continues to have the best known worst-case performance, but for dense graphs (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |E|=\Omega (|V|^{2})}">

</mrow>

</mrow>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |E|=\Omega (|V|^{2})}</annotation>

</semantics>

</math><img src="./471063adbee20b5336610d1d459a8b57f62183ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.79ex; height:3.343ex;" alt="{\displaystyle |E|=\Omega (|V|^{2})}" loading="lazy">) a more recent algorithm by <a href="#CITEREFAltBlumMehlhornPaul1991">Alt et al. (1991)</a> achieves a slightly better time bound, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O\left(|V|^{1.5}{\sqrt {\frac {|E|}{\log |V|}}}\right)}">

<mrow>

<mrow>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

<msqrt>

<mfrac>

<mrow>

</mrow>

</mrow>

<mrow>

</mrow>

</mrow>

</mfrac>

</msqrt>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O\left(|V|^{1.5}{\sqrt {\frac {|E|}{\log |V|}}}\right)}</annotation>

</semantics>

</math><img src="./f18ad5a3faba3805a5a134874e103f40e9fc67fb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:20.856ex; height:7.509ex;" alt="{\displaystyle O\left(|V|^{1.5}{\sqrt {\frac {|E|}{\log |V|}}}\right)}" loading="lazy">. Their algorithm is based on using a <a href="Push-relabel_maximum_flow_algorithm" class="mw-redirect" title="Push-relabel maximum flow algorithm">push-relabel maximum flow algorithm</a> and then, when the matching created by this algorithm becomes close to optimum, switching to the Hopcroft–Karp method.

Several authors have performed experimental comparisons of bipartite matching algorithms. Their results in general tend to show that the Hopcroft–Karp method is not as good in practice as it is in theory: it is outperformed both by simpler breadth-first and depth-first strategies for finding augmenting paths, and by push-relabel techniques.<a href="#cite_note-7">[7]</a>

<div class="mw-heading mw-heading2"><h2 id="Non-bipartite_graphs">Non-bipartite graphs</h2></div>

The same idea of finding a maximal set of shortest augmenting paths works also for finding maximum cardinality matchings in non-bipartite graphs, and for the same reasons the algorithms based on this idea take <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O({\sqrt {|V|}})}">

<msqrt>

</mrow>

</mrow>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O({\sqrt {|V|}})}</annotation>

</semantics>

</math><img src="./71e29921cde091c1bae5116cfc19ff966b7e957a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:8.987ex; height:4.843ex;" alt="{\displaystyle O({\sqrt {|V|}})}" loading="lazy"> phases. However, for non-bipartite graphs, the task of finding the augmenting paths within each phase is more difficult. Building on the work of several slower predecessors, <a href="#CITEREFMicaliVazirani1980">Micali & Vazirani (1980)</a> showed how to implement a phase in linear time, resulting in a non-bipartite matching algorithm with the same time bound as the Hopcroft–Karp algorithm for bipartite graphs. The Micali–Vazirani technique is complex, and its authors did not provide full proofs of their results; subsequently,

a "clear exposition" was published by <a href="#CITEREFPetersonLoui1988">Peterson & Loui (1988)</a> and alternative methods were described by other authors.<a href="#cite_note-8">[8]</a> In 2012, Vazirani offered a new simplified proof of the Micali-Vazirani algorithm.<a href="#cite_note-9">[9]</a>

<div class="mw-heading mw-heading2"><h2 id="Pseudocode">Pseudocode</h2></div>

<pre>/*

G = U ∪ V ∪ {NIL}

where U and V are the left and right sides of the bipartite graph and NIL is a special null vertex

*/

function BFS() is

for each u in U do

if Pair_U[u] = NIL then

Dist[u] := 0

Enqueue(Q, u)

else

Dist[u] := ∞

Dist[NIL] := ∞

while Empty(Q) = false do

u := Dequeue(Q)

if Dist[u] < Dist[NIL] then

for each v in Adj[u] do

if Dist[Pair_V[v]] = ∞ then

Dist[Pair_V[v]] := Dist[u] + 1

Enqueue(Q, Pair_V[v])

return Dist[NIL] ≠ ∞

function DFS(u) is

if u ≠ NIL then

for each v in Adj[u] do

if Dist[Pair_V[v]] = Dist[u] + 1 then

if DFS(Pair_V[v]) = true then

Pair_V[v] := u

Pair_U[u] := v

return true

Dist[u] := ∞

return false

return true

function Hopcroft–Karp is

for each u in U do

Pair_U[u] := NIL

for each v in V do

Pair_V[v] := NIL

matching := 0

while BFS() = true do

for each u in U do

if Pair_U[u] = NIL then

if DFS(u) = true then

matching := matching + 1

return matching

</pre>

<div class="mw-heading mw-heading3"><h3 id="Explanation">Explanation</h3></div>

Let the vertices of our graph be partitioned in <code>U</code> and <code>V</code>, and consider a partial matching, as indicated by the <code>Pair_U</code> and <code>Pair_V</code> tables that contain the one vertex to which each vertex of <code>U</code> and of <code>V</code> is matched, or <code>NIL</code> for unmatched vertices. The key idea is to add two dummy vertices on each side of the graph: uDummy connected to all unmatched vertices in <code>U</code> and vDummy connected to all unmatched vertices in <code>V</code>. Now, if we run a <a href="Breadth-first_search" title="Breadth-first search">breadth-first search</a> (BFS) from uDummy to vDummy then we can get the paths of minimal length that connect currently unmatched vertices in <code>U</code> to currently unmatched vertices in <code>V</code>. Note that, as the graph is bipartite, these paths always alternate between vertices in <code>U</code> and vertices in <code>V</code>, and we require in our BFS that when going from <code>V</code> to <code>U</code>, we always select a matched edge. If we reach an unmatched vertex of <code>V</code>, then we end at vDummy and the search for paths in the BFS terminate. To summarize, the BFS starts at unmatched vertices in <code>U</code>, goes to all their neighbors in <code>V</code>, if all are matched then it goes back to the vertices in <code>U</code> to which all these vertices are matched (and which were not visited before), then it goes to all the neighbors of these vertices, etc., until one of the vertices reached in <code>V</code> is unmatched.

Observe in particular that BFS marks the unmatched nodes of <code>U</code> with distance 0, then increments the distance every time it comes back to <code>U</code>. This guarantees that the paths considered in the BFS are of minimal length to connect unmatched vertices of <code>U</code> to unmatched vertices of <code>V</code> while always going back from <code>V</code> to <code>U</code> on edges that are currently part of the matching. In particular, the special <code>NIL</code> vertex, which corresponds to vDummy, then gets assigned a finite distance, so the BFS function returns true iff some path has been found. If no path has been found, then there are no augmenting paths left and the matching is maximal.

If BFS returns true, then we can go ahead and update the pairing for vertices on the minimal-length paths found from <code>U</code> to <code>V</code>: we do so using a <a href="Depth-first_search" title="Depth-first search">depth-first search</a> (DFS). Note that each vertex in <code>V</code> on such a path, except for the last one, is currently matched. So we can explore with the DFS, making sure that the paths that we follow correspond to the distances computed in the BFS. We update along every such path by removing from the matching all edges of the path that are currently in the matching, and adding to the matching all edges of the path that are currently not in the matching: as this is an augmenting path (the first and last edges of the path were not part of the matching, and the path alternated between matched and unmatched edges), then this increases the number of edges in the matching. This is same as replacing the current matching by the symmetric difference between the current matching and the entire path..

Note that the code ensures that all augmenting paths that we consider are vertex disjoint. Indeed, after doing the symmetric difference for a path, none of its vertices could be considered again in the DFS, just because the <code>Dist[Pair_V[v]]</code> will not be equal to <code>Dist[u] + 1</code> (it would be exactly <code>Dist[u]</code>).

Also observe that the DFS does not visit the same vertex multiple times. This is thanks to the following lines:

<pre>Dist[u] = ∞

return false

</pre>

When we were not able to find any shortest augmenting path from a vertex <code>u</code>, then the DFS marks vertex <code>u</code> by setting <code>Dist[u]</code> to infinity, so that these vertices are not visited again.

One last observation is that we actually don't need uDummy: its role is simply to put all unmatched vertices of <code>U</code> in the queue when we start the BFS. As for vDummy, it is denoted as <code>NIL</code> in the pseudocode above.

<ul><li><a href="Maximum_cardinality_matching" title="Maximum cardinality matching">Maximum cardinality matching</a>, the problem solved by the algorithm, and its generalization to non-bipartite graphs</li>

<li><a href="Assignment_problem" title="Assignment problem">Assignment problem</a>, a generalization of this problem on weighted graphs, solved e.g. by the <a href="Hungarian_algorithm" title="Hungarian algorithm">Hungarian algorithm</a></li>

<li><a href="Edmonds%E2%80%93Karp_algorithm" title="Edmonds–Karp algorithm">Edmonds–Karp algorithm</a> for finding maximum flow, a generalization of the Hopcroft–Karp algorithm</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-1"><a href="#cite_ref-1">^</a> <a href="#CITEREFGabow2017">Gabow (2017)</a>; <a href="#CITEREFAnnamalai2018">Annamalai (2018)</a>

</li>

<li id="cite_note-FOOTNOTEBastMehlhornSchäferTamaki2006-2"><a href="#cite_ref-FOOTNOTEBastMehlhornSchäferTamaki2006_2-0">^</a> <a href="#CITEREFBastMehlhornSchäferTamaki2006">Bast et al. (2006)</a>.

</li>

<li id="cite_note-FOOTNOTEDinitz2006-3"><a href="#cite_ref-FOOTNOTEDinitz2006_3-0">^</a> <a href="#CITEREFDinitz2006">Dinitz (2006)</a>.

</li>

<li id="cite_note-FOOTNOTEPetersonLoui1988-4"><a href="#cite_ref-FOOTNOTEPetersonLoui1988_4-0">^</a> <a href="#CITEREFPetersonLoui1988">Peterson & Loui (1988)</a>.

</li>

<li id="cite_note-FOOTNOTETarjan1983102-5"><a href="#cite_ref-FOOTNOTETarjan1983102_5-0">^</a> <a href="#CITEREFTarjan1983">Tarjan (1983)</a>, p. 102.

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <a href="#CITEREFAhujaMagnantiOrlin1993">Ahuja, Magnanti & Orlin (1993)</a>, section 12.3, bipartite cardinality matching problem, pp. 469–470.

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <a href="#CITEREFChangMcCormick1990">Chang & McCormick (1990)</a>; <a href="#CITEREFDarby-Dowman1980">Darby-Dowman (1980)</a>; <a href="#CITEREFSetubal1993">Setubal (1993)</a>; <a href="#CITEREFSetubal1996">Setubal (1996)</a>.

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <a href="#CITEREFGabowTarjan1991">Gabow & Tarjan (1991)</a>.

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <a href="#CITEREFVazirani2012">Vazirani (2012)</a>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .refbegin{margin-bottom:0.5em}.mw-parser-output .refbegin-hanging-indents>ul{margin-left:0}.mw-parser-output .refbegin-hanging-indents>ul>li{margin-left:0;padding-left:3.2em;text-indent:-3.2em}.mw-parser-output .refbegin-hanging-indents ul,.mw-parser-output .refbegin-hanging-indents ul li{list-style:none}@media(max-width:720px){.mw-parser-output .refbegin-hanging-indents>ul>li{padding-left:1.6em;text-indent:-1.6em}}.mw-parser-output .refbegin-columns{margin-top:0.3em}.mw-parser-output .refbegin-columns ul{margin-top:0}.mw-parser-output .refbegin-columns li{page-break-inside:avoid;break-inside:avoid-column}@media screen{.mw-parser-output .refbegin{font-size:90%}}

/* end https://en.wikipedia.org/ */

</style><div class="refbegin" style="">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFAhujaMagnantiOrlin1993" class="citation cs2"><a href="Ravindra_K._Ahuja" title="Ravindra K. Ahuja">Ahuja, Ravindra K.</a>; <a href="Thomas_L._Magnanti" title="Thomas L. Magnanti">Magnanti, Thomas L.</a>; <a href="James_B._Orlin" title="James B. Orlin">Orlin, James B.</a> (1993), Network Flows: Theory, Algorithms and Applications, Prentice-Hall</cite>.</li>

<li><cite id="CITEREFAltBlumMehlhornPaul1991" class="citation cs2">Alt, H.; Blum, N.; <a href="Kurt_Mehlhorn" title="Kurt Mehlhorn">Mehlhorn, K.</a>; Paul, M. (1991), "Computing a maximum cardinality matching in a bipartite graph in time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \scriptstyle O\left(n^{1.5}{\sqrt {\frac {m}{\log n}}}\right)}">

<mrow>

<mrow>

<msup>

</mrow>

</msup>

<msqrt>

<mfrac>

<mrow>

</mrow>

</mfrac>

</msqrt>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \scriptstyle O\left(n^{1.5}{\sqrt {\frac {m}{\log n}}}\right)}</annotation>

</semantics>

</math><img src="./ba62f94fb7ef836da8c861023ea0b0c74e5933f0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:12.086ex; height:5.509ex;" alt="{\displaystyle \scriptstyle O\left(n^{1.5}{\sqrt {\frac {m}{\log n}}}\right)}" loading="lazy">", Information Processing Letters, 37 (4): 237–240, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0020-0190%2891%2990195-N">10.1016/0020-0190(91)90195-N</a></cite>.</li>

<li><cite id="CITEREFAnnamalai2018" class="citation cs2">Annamalai, Chidambaram (2018), "Finding perfect matchings in bipartite hypergraphs", Combinatorica, 38 (6): 1285–1307, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1509.07007">1509.07007</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs00493-017-3567-2">10.1007/s00493-017-3567-2</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=3910876">3910876</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:1997334">1997334</a></cite></li>

<li><cite id="CITEREFBastMehlhornSchäferTamaki2006" class="citation cs2">Bast, Holger; Mehlhorn, Kurt; Schäfer, Guido; Tamaki, Hisao (2006), "Matching algorithms are fast in sparse random graphs", Theory of Computing Systems, 39 (1): 3–14, <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.395.6643">10.1.1.395.6643</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs00224-005-1254-y">10.1007/s00224-005-1254-y</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2189556">2189556</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:9321036">9321036</a></cite></li>

<li><cite id="CITEREFChangMcCormick1990" class="citation cs2">Chang, S. Frank; McCormick, S. Thomas (1990), A faster implementation of a bipartite cardinality matching algorithm, Tech. Rep. 90-MSC-005, Faculty of Commerce and Business Administration, Univ. of British Columbia</cite>. As cited by <a href="#CITEREFSetubal1996">Setubal (1996)</a>.</li>

<li><cite id="CITEREFDarby-Dowman1980" class="citation cs2">Darby-Dowman, Kenneth (1980), The exploitation of sparsity in large scale linear programming problems – Data structures and restructuring algorithms, Ph.D. thesis, Brunel University</cite>. As cited by <a href="#CITEREFSetubal1996">Setubal (1996)</a>.</li>

<li><cite id="CITEREFDinitz2006" class="citation cs2">Dinitz, Yefim (2006), "Dinitz' Algorithm: The Original Version and Even's Version", in <a href="Oded_Goldreich" title="Oded Goldreich">Goldreich, Oded</a>; <a href="Arnold_L._Rosenberg" title="Arnold L. Rosenberg">Rosenberg, Arnold L.</a>; <a href="Alan_Selman" title="Alan Selman">Selman, Alan L.</a> (eds.), <a rel="nofollow" class="external text" href="https://www.cs.bgu.ac.il/~dinitz/Papers/Dinitz_alg.pdf">Theoretical Computer Science: Essays in Memory of Shimon Even</a> (PDF), Lecture Notes in Computer Science, vol. 3895, Berlin and Heidelberg: Springer, pp. 218–240, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F11685654_10">10.1007/11685654_10</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-32880-3</bdi></cite>.</li>

<li><cite id="CITEREFEdmonds1965" class="citation cs2"><a href="Jack_Edmonds" title="Jack Edmonds">Edmonds, Jack</a> (1965), "Paths, Trees and Flowers", Canadian Journal of Mathematics, 17: 449–467, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.4153%2FCJM-1965-045-4">10.4153/CJM-1965-045-4</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0177907">0177907</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:18909734">18909734</a></cite>.</li>

<li><cite id="CITEREFGabow2017" class="citation cs2"><a href="Harold_N._Gabow" title="Harold N. Gabow">Gabow, Harold N.</a> (2017), "The weighted matching approach to maximum cardinality matching", Fundamenta Informaticae, 154 (1–4): 109–130, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1703.03998">1703.03998</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.3233%2FFI-2017-1555">10.3233/FI-2017-1555</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=3690573">3690573</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:386509">386509</a></cite></li>

<li><cite id="CITEREFGabowTarjan1991" class="citation cs2"><a href="Harold_N._Gabow" title="Harold N. Gabow">Gabow, Harold N.</a>; <a href="Robert_Tarjan" title="Robert Tarjan">Tarjan, Robert E.</a> (1991), "Faster scaling algorithms for general graph matching problems", Journal of the ACM, 38 (4): 815–853, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F115234.115366">10.1145/115234.115366</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:18350108">18350108</a></cite>.</li>

<li><cite id="CITEREFHopcroftKarp1973" class="citation cs2"><a href="John_Hopcroft" title="John Hopcroft">Hopcroft, John E.</a>; <a href="Richard_Karp" class="mw-redirect" title="Richard Karp">Karp, Richard M.</a> (1973), "An n5/2 algorithm for maximum matchings in bipartite graphs", SIAM Journal on Computing, 2 (4): 225–231, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0202019">10.1137/0202019</a></cite>. Previously announced at the 12th Annual Symposium on Switching and Automata Theory, 1971.</li>

<li><cite id="CITEREFKarzanov1973" class="citation cs2"><a href="Alexander_V._Karzanov" title="Alexander V. Karzanov">Karzanov, A. V.</a> (1973), "An exact estimate of an algorithm for finding a maximum flow, applied to the problem on representatives", Problems in Cybernetics, 5: 66–70</cite>. Previously announced at the Seminar on Combinatorial Mathematics (Moscow, 1971).</li>

<li><cite id="CITEREFMicaliVazirani1980" class="citation cs2"><a href="Silvio_Micali" title="Silvio Micali">Micali, S.</a>; <a href="Vijay_Vazirani" title="Vijay Vazirani">Vazirani, V. V.</a> (1980), "An <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \scriptstyle O({\sqrt {|V|}}\cdot |E|)}">

<msqrt>

</mrow>

</mrow>

</msqrt>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \scriptstyle O({\sqrt {|V|}}\cdot |E|)}</annotation>

</semantics>

</math><img src="./1dfea053bbd4136a151cc302c27bb83410029785.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.983ex; height:2.676ex;" alt="{\displaystyle \scriptstyle O({\sqrt {|V|}}\cdot |E|)}" loading="lazy"> algorithm for finding maximum matching in general graphs", <a href="Symposium_on_Foundations_of_Computer_Science" title="Symposium on Foundations of Computer Science">Proc. 21st IEEE Symp. Foundations of Computer Science</a>, pp. 17–27, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FSFCS.1980.12">10.1109/SFCS.1980.12</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:27467816">27467816</a></cite>.</li>

<li><cite id="CITEREFPetersonLoui1988" class="citation cs2">Peterson, Paul A.; Loui, Michael C. (November 1988), "The general maximum matching algorithm of Micali and Vazirani", <a href="Algorithmica" title="Algorithmica">Algorithmica</a>, 3 (1–4): 511–533, <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.228.9625">10.1.1.228.9625</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01762129">10.1007/BF01762129</a>, <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1432-0541">1432-0541</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:16820">16820</a></cite>.</li>

<li><cite id="CITEREFMotwani1994" class="citation cs2"><a href="Rajeev_Motwani" title="Rajeev Motwani">Motwani, Rajeev</a> (1994), "Average-case analysis of algorithms for matchings and related problems", Journal of the ACM, 41 (6): 1329–1356, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F195613.195663">10.1145/195613.195663</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2968208">2968208</a></cite>.</li>

<li><cite id="CITEREFSetubal1993" class="citation cs2">Setubal, João C. (1993), "New experimental results for bipartite matching", Proc. Netflow93, Dept. of Informatics, Univ. of Pisa, pp. 211–216</cite>. As cited by <a href="#CITEREFSetubal1996">Setubal (1996)</a>.</li>

<li><cite id="CITEREFSetubal1996" class="citation cs2">Setubal, João C. (1996), Sequential and parallel experimental results with bipartite matching algorithms, Tech. Rep. IC-96-09, Inst. of Computing, Univ. of Campinas, <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.3539">10.1.1.48.3539</a></cite>.</li>

<li><cite id="CITEREFTarjan1983" class="citation book cs1">Tarjan, Robert Endre (1983). Data Structures and Network Algorithms. CBMS-NSF Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F1.9781611970265">10.1137/1.9781611970265</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-89871-187-5</bdi>.</cite></li>

<li><cite id="CITEREFVazirani2012" class="citation cs2">Vazirani, Vijay (2012), An Improved Definition of Blossoms and a Simpler Proof of the MV Matching Algorithm, CoRR abs/1210.4594, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1210.4594">1210.4594</a>, <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2012arXiv1210.4594V">2012arXiv1210.4594V</a></cite>.</li></ul>

</div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-05-14" href="https://en.wikipedia.org/wiki/?title=Hopcroft%E2%80%93Karp_algorithm&oldid=1290392689">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>